package day1.TraversalBinaryTree;

/**
 * @author pacai
 * @version 1.0
 */
@SuppressWarnings("all")
public class IsBinarySearchTree {
    public static class TreeNode {
        int data;
        TreeNode left;
        TreeNode right;

        public TreeNode(int data) {
            this.data = data;
        }
    }

    public static class Info {
        boolean isBST;
        int max;
        int min;

        public Info(boolean isBST, int max, int min) {
            this.isBST = isBST;
            this.max = max;
            this.min = min;
        }
    }

    public static Info process(TreeNode x) {
        if (x == null) {
            return null;
        }

        Info leftInfo = process(x.left);
        Info rightInfo = process(x.right);

        int max = x.data;
        int min = x.data;
        //保证收集的信息时全集，在递归中无需额外去定制
        if (leftInfo != null) {
            min = Math.min(leftInfo.min, min);
            max = Math.max(leftInfo.max, max);
        }
        if (rightInfo != null) {
            min = Math.min(rightInfo.min, min);
            max = Math.max(rightInfo.max, max);
        }

//        //判断是否是二叉搜素树的两个条件
//        //1.左右子树是否是二叉搜素树
//        boolean isBST = true;
//        if (leftInfo != null && !leftInfo.isBST) {
//            isBST = false;
//        }
//        if (rightInfo != null && !rightInfo.isBST) {
//            isBST = false;
//        }
//        //2.判断左子树的最大值是否小于父结点 判断右子树的最小值是否大于父结点
//        boolean leftMaxLessX = leftInfo == null ? true : leftInfo.max < x.data;
//        boolean rightMinMoreX = rightInfo == null ? true : rightInfo.min > x.data;
//        if (!leftMaxLessX || !rightMinMoreX) {
//            isBST = false;
//        }

        boolean isBST = true;
        boolean leftIsBST = leftInfo == null ? true : leftInfo.isBST;
        boolean rightIsBST = rightInfo == null ? true : rightInfo.isBST;
        boolean leftMaxLessX = leftInfo == null ? true : (leftInfo.max < x.data);
        boolean rightMinMoreX = rightInfo == null ? true : (rightInfo.min > x.data);

        if(leftIsBST && rightIsBST && rightMinMoreX && leftMaxLessX){
            isBST = false;
        }

        return new Info(isBST, max, min);
    }
}
